package cn.zyl.demo.java.sort;

/**
 * ShellSort  类说明: 希尔排序
 * -----------------------------------------------------------------------------------
 * <p>希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。</p>
 * <p>希尔排序是基于插入排序的以下两点性质而提出改进方法的：</p>
 * <p>-插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；</p>
 * <p>-但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；</p>
 * <p>希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序</p>
 *
 * @author wsz
 * @version v1.0
 * @date 2020-08-13
 */
public class ShellSort extends AbstractArraySortSimple{
    /**
     * 排序接口
     * <p>
     *     算法步骤<br>
     *     1.选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；<br>
     *     2.按增量序列个数 k，对序列进行 k 趟排序；<br>
     *     3.每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度
     * </p>
     * @param sourceArray 待排序数组
     * @param order       排序方式，(默认)升序 true；降序 false
     * @return 排序后的数组
     * @throws Exception 异常信息
     */
    @Override
    public Integer[] sort(Integer[] sourceArray, Boolean order) throws Exception {
        Integer[] arr = copyArray(sourceArray);
        //间隔数量（当前分3个批次处理）;数组长度
        int gap = 1,len = arr.length;
        int i,j,tmp;
        start();
        //计算最后一个段的起始位置
        while (gap < len/N_3){
            addOne();
            gap = gap * N_3 + N_1;
        }
        while (gap > 0){
            for(i = gap;i < len;i++){
                tmp = arr[i];
                j = i - gap;
                if(order){
                    //升序
                    while (j >= 0 && arr[j] > tmp){
                        arr[j + gap] = arr[j];
                        j -= gap;
                        addOne();
                    }
                }else {
                    //降序
                    while (j >= 0 && arr[j] < tmp){
                        arr[j + gap] = arr[j];
                        j -= gap;
                        addOne();
                    }
                }
                arr[j + gap] = tmp;
            }
            gap = (int)Math.floor(gap / N_3);
        }
        end();
        return arr;
    }
    public static void main(String[] args) {
        int len =15,max=100;
        //待排序数组初始化
        Integer[] arr = randomArray(len,max);
        AbstractArraySortSimple sort = new ShellSort();
        try {
            System.out.println("升序操作");
            printArray(sort.sort(arr, true));
            System.out.println("降序降序");
            printArray(sort.sort(arr, false));
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}
